00100	PUP6 Paper   			First Draft
00200	
00300	1. OUTLINE
00400		Outline
00500		Abstract
00600		Introduction
00700		Ideas
00800		Implementation
00900		Examples
01000		Performance
01100		Conclusions
01200	
01300	2. ABSTRACT
01400	A system has been implemented which can synthesize large inductive inference
01500	programs from restricted English dialogues.  All knowledge and all
01600	control resides in highly structured pieces of code called BEINGS. Each
01700	BEING has a similar structure, and may therefore be viewed as an extension
01800	of the concept of ACTORS [Hewitt, 1973].  The output code of the system is
01900	also in the form of BEINGS, hence the synthesized program can answer
02000	questions about itself as it runs.   A general description of the
02100	system which realized these ideas is provided, and its target domain is
02200	discussed.  Some unexpected problems, and some unexpected rewards, were
02300	encountered.  Various measures of performance of Automatic Programming 
02400	Systems are proposed, and we compare the current system to previous ones.
02500	We conclude by pooling our ideas into a "view" of Automatic Programming,
02600	and mention future plans.
02700	
02800	2. INTRODUCTION
02900		In this paper we report on a Program-Understanding Program (PUP6)
03000	capable of generating large LISP programs. The methods employed are not
03100	formal, but rather involve structuring of knowledge about programming, about
03200	the task domain, and about transfer of control.  To date, PUP6 has
03300	synthesized three significantly different large (30-page) target programs:
03400	a Winston-like concept formation program [Winston,     ], a grammatical
03500	inference program, and an airline reservation system.  Extended dialogs
03600	are carried on with the user, in a small subset of English, in which the
03700	task is delineated and questionable details are discussed.  Although the
03800	details of these (dialogues and final programs) are the chief concern of
03900	the user, we assume that the reader is interested in studying the ideas
04000	PUP6 embodies, and how they are implemented.  So our treatment will follow
04100	these lines: First, the ideas are presented, including a discussion of
04200	BEINGS.  Next we describe the implementation, and explain our choice of
04300	targets. Only then will we mention performance. Finally, we relate this
04400	work to the field of Automatic Programming.
04500	
     

00100	3. IDEAS
00200		First, we resolve the uniformity vs. structure controversy.  The
00300	benefits of the former include easy addition of knowledge [Newell, l973]
00400	and simple methods for combining information [McCarthy,    ].  Structure,
00500	however, is necessary for efficient handling of large amounts of data. In
00600	PUP6, we integrate these two ideas into the concept of BEINGS.  A BEING is
00700	a collection of about thirty little bits of LISP code; the answers to thirty
00800	questions about the BEING. That is, we view a small program as equivalent
00900	to its answers to these fixed questions. Every scrap of knowledge, every bit of
01000	control structure should be encoded into BEINGS. There is nothing else in
01100	the system but this interacting community.  Notice that while each BEING is
01200	highly structured, this structure is uniform over the entire community. Each
01300	BEING part is itself a little BEING, etc., and we stop this infinite regress
01400	when the contents of the BEING part becomes meaninglessly primitive. Each
01500	BEING is cognizant of the set of thirty questions, and in answering one of
01600	them it may freely ask quesions of other BEINGS (often through nondetermi-
01700	nistic goal statements.)  The reader may glance below at the particular set
01800	of questions used, but we shall discuss our other ideas next.
01900		Since only BEINGS exist, all our code must be written as BEINGS, and
02000	must be written by BEINGS.  A crucial consequence is that _some_ BEINGS must
02100	write code. Our new idea is that the BEING who knows about X takes charge of
02200	generating code relating to X. For example, the SORT BEING can do sorting, and
02300	he can also write specialized sort routines, and he can answer questions about
02400	sorting.  A second consequence is that the output code will have all the
02500	"intelligence" that any BEING community has: it can write variations of itself,
02600	modify itself according to the user's complaints, and answer questions about
02700	what it is doing as it runs.
02800		In a similar vein, _some_ BEING(s) must do the translation of the 
02900	users' quasi-English inputs into BEING-usable form.  We choose to have each
03000	BEING X recognize English related to X.  Thus translation consists of
03100	querying "who can recognize ..." and waiting for a response. For example, 
03200	our  SORT BEING must also recognize and process phrases involving sorting or
03300	ordering.
03400		Three more ideas are present, constraints which reflect the author's
03500	philosophy:  one need not feel any reverence toward the anthropomorphic
03600	paradigm of programming (ignore details, catch them by blind debugging.)
03700	As in all programming, decisions continually crop up which the system is 
03800	not able to resolve at the time. We have the system spend a significant
03900	effort deferring the decision as long as possible. When, at last, no
04000	progress can be made without its resolution, if the system is still
04100	unsure, either the user settles the question or else a backtrack point is
04200	reluctantly set up.  If there are two or more decisions which can no longer
04300	be deferred, we tackle first the one estimated to be the easiest  [see
04400	Dijkstra et al, 1972].  The final bit of philosophy is that most of the
04500	carelessness bugs can be eliminated through this deferral and through
04600	very precise record-keeping.  Humans depend on their adaptability to 
04700	compensate for limitations in their brain hardware [see Newell and Simon,
04800	1973] but there is no need for an _automatic_ programming system to do so.
     

00100	4. IMPLEMENTATION
00200		The realization of any large system is worth study, since there
00300	seems to be a limit to the size of a program before it becomes unmanageable
00400	[Dijkstra et al, 1972] for humans.  Since PUP6 is 200 pages long, yet took
00500	only hundreds of man-hours, we shall describe how it was created.
00600		Considerable attention was spent on choosing an appropriate domain
00700	of target programs.  We now discuss our choice:  inductive inference.
00800	The obvious difficulty appears to be the size of the programs involved: they
00900	are two orders of magnitude larger than previously synthesized programs. But
01000	there are four big attractions:
01100	(i) A wide range of complexity exists, from a one-page sequence extrapolator
01200		to Meta-Dendral.
01300	(ii) Each increasingly sophistocated inductive inference (II) program uses
01400		many of the concepts embodied in simpler II programs.
01500	(iii) If a super-human target program is ever written, it could itself
01600		contribute to the field of Automatic Programming!
01700	(iv) Since we are the "experts" on inductive inference ourselves, our
01800		reliance on introspection is as valid -- and potentailly as
01900		valuable -- as Dendral's chemists' protocols.
02000	
02100	After studying many sample programs from the II domain, the author selected
02200	sequence extrapolation as a reasonable beginning task. It was quickly learned
02300	that this was too easy: humans have only a few techniques for extrapolating
02400	sequences, and a very limited capacity for composing them.   Thus a rather
02500	rigid sequence extrapolator writer may be capable of generating a large
02600	class of super-human programs (see section   on SEW, in Green et al, 1974].
02700		The next candidates were grammatical inference and concept formation.
02800	Determined  not to choose too simple a task again, the latter program was
02900	finally decided upon. We took as our taret Winston's [19  ] system, but
03000	decided that our PUP should possess much more domain-specific knowledge
03100	than is strictly necessary to write that one program.  To make the goal
03200	more tractible, certain parts of Winston's description were ignored, namely
03300	the heuristic graph-matching section, and the consistency requirement
03400	that relations on features be functionally indistinguishable from features.
03500		The program repeatedly scans a scene and tries to name it. The scene
03600	is broken into a set of features, each of which is a relation on some
03700	objects in the scene.  Internally, the program maintains a model for
03800	each distinct concept it has been told about. The model contains a
03900	description of the objects expected in the scene, a set of features
04000	which must be present in the scene (else it can't be the same as this
04100	concept), a set of features which must not be present in the scene,
04200	and a list of features which may or may not be present.  When confronted
04300	by a new scene, the program must scan its models until it finds one
04400	which matches it. That is, all the model's MUST features are present,
04500	and all the MUSTNOT features are absent from the observed scene.  It
04600	informs the user of this guess, and accepts the proper concept name.
04700	If it guessed incorrectly, it modifies its models. The wrong guess
04800	model may have features added to its MUST or MUSTNOT sets; the correct
04900	concept name model may have to be added (if it's a new concept) or
05000	updated as well.
05100		For example, a scene might be: OBJECTS a,b,c,d
05200	(GREEN a)(BLUE c)(TOUCHING c d)(SUPPORTS a c)(SUPPORTS b c).
05300	A model for an arch might be OBJECTS a,b,c
05400			MUST 	(SUPPORTS a c)(SUPPORTS b c)
05500			MUSTNOT (TOUCHES a b)
05600			MAY	(GREEN a)(WEDGE c)(PRISM a)(BLOCK b)(PARALLEL a b)
05700	
05800		After the target program (concept formation) was chosen, it was
05900	rewritten cleanly, as a structured program [Gadwa, l973].  Next a complete
06000	dialogue was simulated between the user and a human programmer
06100	who played the role of a reasonable AP system, similar to studies by
06200	Balzer [197 ].  The dialog was then annotated: after each user response,
06300	comments were inserted which described the "states" the system-player had
06400	gone through before printing his next response.  This included blind paths
06500	which were tried, use of outside world knowledge, and, in general, was meant
06600	to be the "intelligence" necessary to do the task.  Our fear was that a
06700	system could be built which synthesized the concept formation program, and
06800	yet was so unintelligent that we learned nothing from it.  We hoped that
06900	any system which (i) got the target program correctly, (ii) followed our
07000	initial dialogue, and, most importantly, (iii) went through the same line
07100	of reasoning before responding that our comments indicated the human
07200	followed,  would be far along the road toward intelligence.
07300		At this point, we developed most of the ideas described in the
07400	preceding section, and chose a rough initial set of BEINGS. Each one had
07500	not much more than a name and a vague description of what it must do.
07600	The dialog was gone through again, painstakingly, and the comments were
07700	replaced by a description of which beings would call which other beings,
07800	why, and the results of each such call.  Our contraints on each being
07900	thus grew, sometimes changed, and occasionally a new BEING or BEING part had
08000	to be added to the community. This process was long (200 hours) and produced
08100	a long (200 pages) protocol, actually a hand trace of the system execution.
08200	About seventy BEINGS were needed, a dozen of which we viewed as domain-
08300	specific and the rest of which were domain-independent programming
08400	knowledge.  About thirty different BEING parts were called for, and they
08500	are listed in Appendix 1.  The next appendix describes each BEING briefly;
08600	only the most important knowledge is mentioned.
08700		A result of our method of incremental specification of BEINGS is
08800	that each BEING has only those parts which are going to be used sometime
08900	during the ensuing dialogue.  Many presentations of the resultant data are
09000	possible; in Appendix 1, for each BEING part, we give the percentage of
09100	BEINGS which had to have this part specified for them. In Appendix 2,
09200	for each BEING, we mention the number of of its parts we specified. On
09300	the average, each BEING part was present in   % of all BEINGS, and, also
09400	on the average, each BEING had     of its 30 parts specified.
09500		During the programming, 100 small functions were written to supple-
09600	ment the language. Most were typical current AI language features (pattern-
09700	matching, demons, special data types) or tiny additions to INTERLISP (flatten,
09800	set-difference) or functions which manage BEINGS (add-a-new-being,
09900	print-a-being's-parts). We had to relax our principle that "everything is
10000	BEINGS" in the interests of efficiency and feasibility of coding.  The
10100	initial programming took only a hundred hours, but several times that
10200	amount of work was required before the system was debugged to the point
10300	of successfully following the annotated dialogue.
     

00100	5. EXAMPLES
00200		Now we shall present examples of the following: programming
00300	knowledge BEING,  concept formation knowledge BEING,  and a description
00400	of a piece of the user-PUP6 dialogue.
00500		The OBTAIN_USABLE_INFORMATION  BEING is a typical, high-level,
00600	domain-independent creature.  The WHEN part informs us that this
00700	is always undesirable (-10) but may be indicated (+111) if there exists
00800	new but not yet usable information.  The META-CODE has us choose from the
00900	following four alternatives, each of which is itself a BEING:  translate
01000	something, get brand new information, analyze the implications of some
01100	existing information, extract a small, relevant subset of the existing
01200	information to concentrate upon.
01300		To PARTITION_A_DOMAIN in an inductive manner, we must make a few
01400	choices. The partition may be only partial, it may be only weak, and, most
01500	importantly, the BEING should partition by doing only some of these:
01600	accept a class-name and get some of its elements, accept an element and
01700	get its class-name, accept <element, class-name> pairs. Other beings know
01800	about each of these alternatives. During the partitioning, the only new 
01900	demon to keep active is the one called fringe-of-conciousness.
02000		The dialogue begins by PUP6 asking the user for any task. The user
02100	replies, "Write a program which does concept formation." There are many
02200	decisions that PUP6 knows about in writing a specialized concept formation
02300	program, and it manages to defer them all.  For example, it must choose
02400	between classificatory, comparitive, and metrical concept formation. Since
02500	all three involve partitioning a domain of examples, PUP6 decides it can
02600	defer this choice until after code for the partitioning is synthesized.
02700	Hours later, the system asks the user to make this decision, he picks the
02800	first alternative, which involves only partitioning, and the system prints
02900	that it has finished the task!  
03000		About a third of the way into the dialogue, the system learns it must
03100	compare the input scene against its internally stored models of concepts,
03200	until it finds one which doesn't fail the comparison. It asks the user
03300	what it means for scene S to fail the comparison to model M. The user 
03400	replies, "M is incompatible with the observed features of S."
03500	The IDEN part of the CONTRADICTS BEING recognizes this sentence pattern,
03600	and transforms it to (FORSOME F IN M_FEATURES (CONTRADICTS F S_FEATURES)).
03700	The BEING which inserts this into the synthesized code requires that the
03800	user pick some proper name for the function CONTRADICTS; say the user
03900	types in #.  The function FORSOME is so primitive that no specialized
04000	version of it is written normally.  The system informs the user of where
04100	it is by means of a cursor pointing into a graph of program code. This is
04200	analogous to the textual and dynamic indices which  Dijkstra suggests.
04300	Later in the dialogue, PUP6 decides it must expand the function #.  The
04400	being CONTRADICTS is again called on, this time  being asked how to write
04500	a specialized version of a contradiction test.  It replies that SOME_OF
04600	the following types of contradictionmay occur: PROBABILITY:0,
04700	PROBABILITY:1, and PROBABILITY:ε(0,1).  The SOME_OF BEING takes control,
04800	and asks if the decision can be deferred.  The deferral being looks about,
04900	first asking if there is any non-null piece of code that all three have
05000	in common. This fails, and eventually the deferral being reports failure.
05100	SOME_OF  sees it has no basis upon which to form a guess, and asks the user.
05200	ASK_USER takes over, and quickly finds out what it is that PUP6 wants to
05300	learn. The names of the three choices are so cryptic, that their WHAT and
05400	HOW parts are printed out to the user, as well as their names.  The user
05500	types back his choices, in our case all three.  SOME_OF composes three new
05600	function calls, separated by a conditional:
05700	  (COND ( (MEMBER             F   PROBABILITY:0_PART_OF_M_FEATURES)
05800		  (PROBABILITY:0_#    F   S_FEATURES))
05900	        ( (MEMBER             F   PROBABILITY:1_PART_OF_M_FEATURES)
06000		  (PROBABILITY:1_#    F   S_FEATURES))
06100	        ( (MEMBER             F   PROBABILITYε(0,1)_PART_OF_M_FEATURES)
06200		  (PROBABILITYε(0,1)_#  F  S_FEATURES))
06300	A trichotomy demon recognizes this as a split on a function's values being
06400	=0, =1, or between zero and one.  It asks whether this particaular function
06500	can only range inside the interval [0,1].  Probability answers affirmatively
06600	so SOME_OF replaces the final test by the constant T. Later on, PUP6 must
06700	worry about the other two tests, and about the three contradiction
06800	predicates.  These guys know that they are immediately encodable; a
06900	probability=0 contradiction means that arg1 must not occur in the world arg2
07000	yet it does. So it is defined as (MEMBER arg1 arg2).  A probability=1
07100	contradiction occurs when a feature arg1 must occur in the world arg2, yet
07200	it doesn't. SO its definition is simply (NOT (MEMBER arg1 arg2)).   It is
07300	impossible for a feature with probability in (0,1) to be in contradiction
07400	with any world, so this third predicate is defined as the constant NIL.
07500	IS_OF_TYPE recognizes that it must replace each of the two case tests,
07600	unless M_FEATURES is organized permanently into three parts.  The structure-
07700	inducing being will take over.  He finds nothing about this tripartite
07800	structuring which could damage any earlier synthesized code, and asks the
07900	user's blessing.  Notes are added to the list of coding warnings that
08000	any reference to the entire list of M_FEATURES must be replaced by either
08100	APPEND of the three new lists, or else by three separate statements. 
08200	GET_NAME is indirectly called, and he has the user name the three new
08300	lists of features; say he responds by calling them MUSTNOT, MUST, and MAY.
08400	The system would at this point draw an arrow on its graph of code, from
08500	the function call (# F S_FEATURES) to the new block of code:
08600	  (COND ( (MEMBER        F   MUSTNOT_LIST_OF_M)
08700		  (MEMBER        F   S_FEATURES))
08800	        ( (MEMBER        F   MUST_PART_OF_M)
08900		  (NOT (MEMBER   F   S_FEATURES))
09000	        (  T (COMMENT THIS "T" IS OK IN PLACE OF "MEMBER F MAY_PART_OF_M")
09100		   NIL))
09200	Notice that only a few messages have passed back and forth during
09300	all this processing; this shows the utility of having an annotated dialogue
09400	to compare against the actual trace. The user has the feeling of merely
09500	directing, constraining, and watching the activites of a busy programmer.
     

00100	6. PERFORMANCE
00200		The character of the dialogue just decribed is, of course, one
00300	important measure of the intelligence of an AP system.  One which asked
00400	"What is the first instruction? What is the second..."  would be universal
00500	but worse than useless. In this section we propose some questions one
00600	should ask when confronted by a new AP system, some measures of performance
00700	of an AP system, and we apply these to PUP6 and some earlier AP programs.
     

00100	7. CONCLUSIONS
     

00100	8. ACKNOWLEDGEMENTS
00200	
00300		There are, of course, countless ideas embodied in any concrete
00400	project.  Sweeping philosophical assumptions are made simply in trying to
00500	do Automatic Programming [McCarthy, l9  ].   Any Program-Understanding
00600	Program should include the best parts of all the best old ideas.
00700	We rely on concepts gleaned from Actors [Hewitt, l973], Demons [Charniak,
00800	1973], heterarchy [Reddy, l973], structured programming [Dijkstra, l973],
00900	assertional data bases and flexible data types [Sacerdoti, 1973], pattern-
01000	directed invocation of procedural knowledge [Winograd, l972], the paradigm
01100	of dialogue [Floyd, 1972], and studies on program specification techniques
01200	[Green, l974].  Of course this list is incomplete; sophistocated ideas are
01300	captured in the languages themselves: QLISP [Sacerdoti], INTERLISP 
01400	[Teitelmann, l97 ], LISP [McCarthy, l9  ], and English [Anon.].  To this
01500	rich store, one may acheive new heights merely by synergy.
01600		The success of the BEINGS project, as well as the precursor PUP
01700	programs [Green et al., 1974] is due in large measure to the encouragement,
01800	advice, support, and creative enrgy of C. Cordell Green.  I have also drawn
01900	upon discussions with the SAIL Auotmatic Programming Group, and in par-
02000	ticular with R. Waldinger, D. Barstow, B. McCune, D. Shaw, and L. Steinberg.